High Efficiency Video Coding (HEVC) is a new coding standard that has been developed in recent years. In the High Efficiency Video Coding (HEVC) system, the fixed-size macroblock of H.264/AVC is replaced by a flexible block, named coding unit (CU). Pixels in the CU share the same coding parameters to improve coding efficiency. A CU may begin with a largest CU (LCU), which is also referred as coded tree unit (CTU) in HEVC. In addition to the concept of coding unit, the concept of prediction unit (PU) is also introduced in HEVC. Once the splitting of CU hierarchical tree is done, each leaf CU is further split into one or more prediction units (PUs) according to prediction type and PU partition.
Along with the High Efficiency Video Coding (HEVC) standard development, the development of extensions of HEVC has also started. The HEVC extensions include Range Extension (RExt) and screen content coding (SCC). Due to specific characteristics of screen contents, coding tools have been developed and demonstrate significant gains in coding efficiency. Among them, the color index coding (a.k.a. major color based coding) techniques represent block of pixels using indices to the palette (major colors), and encode the palette and the indices by exploiting spatial redundancy. While the total number of possible color combinations is huge, the number of colors in an area of picture is usually very limited for typical screen contents. Therefore, the color index coding becomes very effective for screen content materials. Related key color index coding techniques are briefly reviewed as follows.
Current CU Syntax in RExt with Adoption of IntraBC
The IntraBC (Intra Block Copy) technique that was originally disclosed in JCTVC-M0350 (Budagavi et al., AHG8. Video coding using Intra motion compensation, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 13th Meeting: Incheon, KR, 18-26 Apr. 2013, Document: JCTVC-M0350) has been adopted into HEVC along with JCTVC-N0256 (Pang, et al. Non-RCE3: Intra Motion Compensation with 2-D MVs, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC
JTC 1/SC 29/WG 11, 14th Meeting: Vienna, AT, 25 Jul. 2 Aug. 2013, Document: JCTVC-N0256). The adopted IntraBC method is signaled in coding unit syntax according to High Efficiency Video Coding (HEVC) Range Extension Text Specification: Draft 4 (Flynn, et al., “High Efficiency Video Coding (HEVC) Range Extension Text Specification: Draft 4”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 14th Meeting: Vienna, AT, 25 Jul. -2 Aug. 2013, Document: JCTVC-N1005). Table 1 shows the coding unit syntax for IntraBC as disclosed in JCTVC-N1005.
TABLE 1Notecoding_unit( x0, y0, log2CbSize ) { if( transquant_bypass_enabled_flag )  cu_transquant_bypass_flag if( slice_type != I )  cu_skip_flag[ x0 ][ y0 ] nCbS = ( 1 << log2CbSize ) if( cu_skip_flag[ x0 ][ y0 ] )  prediction_unit( x0, y0, nCbS, nCbS ) else {  if( intra_block_copy_enabled_flag )(1-1)   intra_bc_flag[ x0 ][ y0 ](1-2)  if( !intra_bc_flag[ x0 ][ y0 ] ) {(1-3)   if( slice_type != I )(1-4)    pred_mode_flag(1-5)   if( CuPredMode[ x0 ][ y0 ] != MODE_INTRA ∥(1-6)    log2CbSize = = MinCbLog2SizeY )    part_mode(1-7)  }   ......
As shown in Table 1, when IntraBC is enabled as indicated by Note (1-1), intra_bc_flag is signaled as indicated by Note (1-2). If intra_bc_flag is not equal to 1 as indicated by Note (1-3), whether the slice is not an I-slice is checked as indicated by Note (1-4). If so, pred_mode_flag is signaled as indicated by Note (1-5). Furthermore, whether the current prediction is not Intra mode or whether the current CU is the smallest CU (SCU) is checked as indicated by Note (1-6). If so, part_mode is signaled to indicate the partition mode as indicated by Note (1-7).
Major-Color-Based (or Palette) Coding Techniques
Two palette coding techniques have been evaluated in RExt core experiments. The first one is disclosed I JCTVC-00182 (Guo et al., Evaluation of Palette Mode Coding on HM-12.0+RExt-4.1, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG11, 15th Meeting: Geneva, CH, 23 Oct.-1 Nov. 2013, Document: JCTVC-00218), where a very simple but efficient histogram based algorithm is used to classify the pixels. In specific, the most significant N peak values in the histogram are selected as major colors, as shown in FIG. 1. For lossy coding, the pixel values that are close to a major color are quantized to a major color. For example, in FIG. 1, the quantization step is q, and the quantization zone around a major color, i.e. between the two dotted lines, is 2q. In other words, any pixel value between the two quantization levels is quantized to the representative major color and the selected major color is identified by a corresponding major color index. Other pixels that do not belong to any major color sets are named escape pixels or escape colors, which may also be quantized before coding. For lossless coding, none of the quantization processes is used. For each pixel, a color index is assigned to indicate which color set it belongs to. If N major colors are used, the values from 0 to (N−1) are used as indices for the N major sets and the largest index value (i.e., index N) is used to indicate the pixel belonging to the escape pixel set.
After classification, the pixels of a block can be converted into color indices. Then, a predictive coding method is applied to the indices, where a pixel line can be predicted by different modes. In specific, three kinds of line modes are used for a pixel line, i.e. horizontal mode, vertical mode and normal mode. In the horizontal mode, all the pixels in the same line have the same value. If the value is the same as the first pixel of the above pixel line, only line mode signaling bits are transmitted. Otherwise, the index value is also transmitted. In the vertical mode, the current pixel line is the same as the above pixel line. Therefore, only line mode signaling bits are transmitted. In normal mode, pixels in a line are predicted individually. For each pixel, the left or above neighbor is used as a predictor, and the prediction symbol is transmitted to the decoder.
The second variant of palette coding technique is disclosed in JCTVC-N0249 (Guo, et al., “Non-RCE3: Modified Palette Mode for Screen Content Coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 14th Meeting: Vienna, AT, 25 Jul.-2 Aug. 2013, Document: JCTVC-N0249). The differences with the first approach are (1) “pixel mode” is removed and all the pixel values are converted to palette indices for encoding, (2) the possible error (from pixel values to palette indices) is encoded using the HEVC residue coding method, and (3) the palette index and the “run” are shared by all three color components.
All previously proposed palette coding techniques are applied to coding units, i.e. the palette coding process and signaling are at the CU level. For example, the CU syntax for JCTVC-00182 and JCTVC-N0249 is illustrated in Table 2.
TABLE 2Notecoding_unit( x0, y0, log2CbSize ) { if( transquant_bypass_enabled_flag )  cu_transquant_bypass_flag palette_mode_flag if (palette_mode_flag) {  ...... } if( slice_type != I )  cu_skip_flag[ x0 ][ y0 ] nCbS = ( 1 << log2CbSize ) if( cu_skip_flag[ x0 ][ y0 ] )  prediction_unit( x0, y0, nCbS, nCbS ) else {  if( intra_block_copy_enabled_flag )   intra_bc_flag[ x0 ][ y0 ]  if( !intra_bc_flag[ x0 ][ y0 ] ) {   if( slice_type != I)    pred_mode_flag   if( CuPredMode[ x0 ][ y0 ] != MODE_INTRA ∥    log2CbSize = = MinCbLog2SizeY )    part_mode  {  ......
Palette Coding
Palette coding mode has been included in HEVC Screen Content Coding, JCTVC-R-1005 (Joshi, et al., High Efficiency Video Coding (HEVC) Screen Content Coding: Draft 1, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 18th Meeting: Sapporo, JP, 30 Jun.-9 Jul. 2014, Document: JCTVC-R1005). According to JCTVC-R1005, a palette is utilized to represent a given video block (e.g. CU) with limited number of values. Some related terms are illustrated as follows.
1. Palette table: A mapping table to map from a pixel value to an index
2. Color index map: Mapped pixel indices associated with values in the current block
3. Palette predictor: In SCM-3.0 (Joshi, et al., Screen content coding test model 3(SCM 3), Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 19th Meeting: Strasbourg, FR, 17-24 Oct. 2014, Document: JCTVC-S1014), the palette table of last coded palette CU is used as predictor for current palette table coding. In palette table coding, a palette_share_flag is first signaled. If palette_share_flag is 1, all the palette colors in the last coded palette table are reused for the current CU. The current palette size is also equal to the palette size of last coded palette CU. Otherwise (i.e., palette_share_flag being 0), the current palette table is signaled by choosing which palette colors in the last coded palette table can be reused, or by transmitting new palette colors. The size of the current palette is set to the size of the predicted palette (i.e., numPredPreviousPalette) plus the size of the transmitted palette (i.e., num_signaled_palette_entries). The predicted palette is a palette derived from the previously reconstructed palette coded CUs. The last used palette size and the palette predictor size will be updated each time when palette mode is enabled. When coding the current CU as palette mode, those palette colors which are not predicted using the predicted palette are directly transmitted into the bitstream.
The decoding and parsing processes according to JCTVC-R0348 (Onno, et al, “Suggested combined software and text for run-based palette mode”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 18th Meeting: Sapporo, JP, 30 Jun.-9 Jul. 2014, Document: JCTVC-R0348) are briefly described as follows.
1. Signaling of the palette:
1.1 Signal “palette sharing flag” first, which indicates whether the palette predictor is used as the current palette. If it is true, the following processes in step 1.2 to 1.4 are skipped.
1.2 Signal “reused flags” to indicate which elements of the palette predictor are used in the current palette.
1.3 Signal ‘number of non-predicted elements’ which indicate how many elements in current palette are not predicted from the palette predictor.
1.4 Signal the value of each non-predicted element.
2. Signaling of the color index map:
2.1 The pixels in the block can be coded in horizontal raster scan order, vertical raster order, horizontal traverse scan order or vertical traverse order.
2.2 For each position, a flag is first transmitted to indicate which prediction mode between “copy above mode” and “new run mode” is being used.
2.3 When “copy above mode” is used, “number of runs” follows the flag. For the number of runs, the indices are the same as those in above line along the scan order.
2.4 When “new run mode” is used, “index” is signaled after the flag.
2.4.1 When the “index” is “ESCAPE”, the pixel value itself is signaled.
2.4.2 When the “index” is in the palette table, “number of runs” is signaled. For the number of runs, the indices are same as the index signaled.
It is desirable to improve the coding efficiency associated with color index map coding.